class Solution {
    /*
        思路: 对于奇数 d[i] = d[i] + 1;
                 偶数 d[i] = d[i/2];
    */
    public int[] countBits(int n) {
        int[] d = new int[n+1];
        d[0] = 0;
        for(int i=1; i<=n; i++){
            d[i] = d[i>>1] + (i&1);
        }
        return d;
    }
}